\input basic
\output {\page}
\magnify {1100}
\parindent 0 pt
\parskip 12 pt

\ctrline {CS154 PROBLEM SET 1, SOLUTIONS}

1.4

In order to show that the two definitions are equivalent it is necessary
to show two things:\ \ (I) that if a string, $s$, satisfies definition (1)
then $s$ satisfies definition (2), and (II) that if a string, $s$, satisfies
definition (2), then $s$ satisfies definition (1).

We start by showing (I).  The proof is by induction on the length of $s$.
If $|s| = 0$, then $s = \epsilon$, whence $s$ satisfies definition (2).  This
establishes our basis.  Suppose that (I) is true whenever $|s| < n$, for some
$n > 0$.  We now show that (I) is true whenever $|s| = n$; this will complete
the induction.

Choose any string, $s$, that satisfies definition (1), such that $|s| = n$.
Let $x$ be the shortest prefix of $s$ having an equal number of $($'s and
$)$'s; such an $x$ must exist,
because $s$ has at least one such prefix, namely itself.  We now consider
two cases.

Case 1 ($x = s$):\ \ Since $s$ satisfies (1b), its first character must be
a $($.  Definition (1b) also tells us that the first $n-1$
characters of $s$ include at least as many $($'s as $)$'s.  Since (1a) tells
that $s$ has exactly as many $($'s as $)$'s, the last character of $s$
must be a $)$.  Thus we can write $s$ as $(t)$.  I claim that $t$ satisfies
definition (1).  $t$ contains as many $($'s as $)$'s, just one fewer of
each than $s$ contains; therefore $t$ satisfies (1a).  Let $p$ be a prefix
of $t$.  Suppose now that $t$ does not satisfy (1b).  Let $p$ be the shortest
prefix of $t$ that has more $)$'s than $($'s.  Then $t$ has just one more
$)$ than $($'s.  Therefore the string, $(t$ has an equal number of $($'s
and $)$'s, contrary to how we constructed $x$.  Therefore $t$ must satisfy
(1b).  Therefore $t$ satisfies definition (1).  By the inductive hypothesis,
$t$ satisfies definition (2).  By (2a), therefore, $(t)$ satisfies definition
(2).  In other words, $s$ satisfies definition (2).

Case 2 ($|x| < n$):\ \ Then $s$ is of the form $xy$, where neither $x$ nor
$y$ is the empty string.  $x$ was chosen to have an equal numbers of $($'s
and $)$'s.  Since $s$ also has an equal number of $($'s and $)$'s, $y$
must therefore have an equal number of $($'s and $)$'s.  Therefore $x$ and
$y$ both satisfy (1a).  By (1b), the first character of $s$ is $($; therefore
the first character of $x$ is $($.  Define the excess of a string as the
number of $($'s minus the number of $)$'s.  The excess of the first non-trivial
prefix of $x$ is $1$.  Because of the way we constructed $x$, the excess
of any of its prefixes is never $0$.  Since the excess changes by $1$ from
one prefix to the next longer one, the excess can never be negative.  Therefore
$x$ satisfies (1b).  Now we need to show that $y$ satisfies (1b).  Let $p$
be a prefix of $y$.  Since $xp$ is a prefix of $s$, it has at least as many
$($'s as $)$'s.  Therefore $p$ has at least as many $($'s as $)$'s.  Thus
$y$ satisfies (1b).  By the inductive hypothesis, $x$ and $y$ both satisfy
definition (2).  Therefore $xy$ satisfies definition (2).  In other words,
$s$ satisfies definition (2).

Thus, we have shown (I), by induction.

We now prove (II) by induction on the length of $s$.  If $|s| = 0$ then
$s$ obviously satisfies (1a) and (1b), so that our base case is established.
Suppose that (II) is true whenever $|s| < n$, for some $n > 0$.  We will show
that (II) is true whenever $|s| = n$, completing the induction.

Suppose that $|s| = n$ and that $s$ satisfies definition (2).  Since $n > 0$,
$s$ is of the form $(w)$ where $w$ satisfies definition (2) or of the form
$wx$ where $w$ and $x$ both satisfy definition (2) and neither $w$ nor $x$
is equal to $s$.

Case 1, $s = (w)$:\ \ By the inductive hypothesis, $w$ satisfies definition
(1).  It is easy to see that $s$ must therefore satisfy definition (1).

Case 2, $s$ = $wx$:\ \ Both $w$ and $x$ are shorter than $x$.  Therefore,
by the inductive hypothesis, they satisfy definition (1).  It is easy to
see that $s$ must therefore satisfy definition (1).

Thus, by induction, if $s$ satisfies definition (2) then $s$ satisfies
definition (1).

Having now shown (I) and (II), we have shown that definitions (1) and (2)
are equivalent.

1.5

The basis is correct, and the inductive step is correct for all $n > 2$
($S↓{1}$ is supposed to contain the first $n-1$ elements of $S$, and
$S↓{2}$ is supposed to contain the last $n-1$ elements of $S$; for $n > 2$,
these two sets have at least one element in common).

However the inductive step is invalid for $n=2$, since no matter how we
write $S$ as the union of two singleton sets, the singleton sets will
not have any elements in common.

1.6

It is not hard to verify that each of the given relations is reflexive,
transitive, and symmetric, and hence an equivalence relation.
I will only give the equivalence classes.

(a) The set of equivalence classes is 
$$\{\{i\}| i \hbox{\rm\ is an integer}\}.$$
Note that each equivalence class is a set with a single element.

(b) The set of equivalence classes is
$$\{ \{q | q \hbox{\rm\ was born at the same
hour of the same day of some year as}\ p \} | p\hbox{\rm\ is a person}\}.$$
Note that the equivalence classes are sets of people, not times.
I have written the equivalence classes in this funny way, to make sure
that they are non-empty.  Only one student noticed this fine point.

(c) The set of equivalence classes is
$$\{ \{q | q\hbox{\rm\ was born at the same
hour of the same day of the same year as}\ p \} | p\hbox{\rm\ is a person}\}.$$
Note that there are only finitely many equivalence classes, because there
are only finitely many people.

1.7

Transitive closure:\ \ $\{ (1,2), (2,3), (3,4), (5,4), (1,3), (2,4), (1,4) \}$

Reflexive and transitive closure:\ \ $\{ (1,2), (2,3), (3,4), (5,4), (1,3),
(2,4), (1,4), (1,1), (2,2), (3,3), (4,4), (5,5) \}$

Symmetric closure:\ \ $\{ (1,2), (2,1), (2,3), (3,2), (3,4), (4,3),
(5,4), (4,5) \}$

1.9
Let $R$ be a symmetric, transitive, irreflexive relation, as desired.  Then there
is some element of $R$'s domain, call it $a$, such that $a \not\mathrel{R} a$.
If $a \mathrel{R} b$, for some $b$, then by symmetry, $b \mathrel{R} a$.
Transivity applied to these two statements implies $a \mathrel{R} a$.
Thus $a \mathrel{R} b$ must be false for all $b$.

This is all we need to know in order to construct a solution.  For example,
we may take $R$ to be the empty relation on any non-empty domain.  Another
example is $R = \{(0,0)\} \hbox{\rm\ defined on the domain}\ \{0,1\}$.

Alternative reasoning (Toby Yamagiwa):\ \ In (1.8) you needed the
reflexive property to show that the union of equivalence classes contains
all elements of $S$.  [Therefore, we must define $R$ so that some element
of its domain is in no equivalence class$\ldotss$]

\vfill\eject\end